package com.hy;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:第二个更大的元素
 * author: Mr.Du
 * Date: 2023/12/13
 * Time: 10:32
 */
public class SecondGreaterElement {

    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        // 存放答案的数组
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();
        // 倒着往栈里放
        for (int i = n - 1; i >= 0; i--) {
            // 判定个子高矮
            while (!s.isEmpty() && nums[s.peek()] <= nums[i]) {
                // 矮个起开，反正也被挡着了。。。
                s.pop();
            }
            // nums[i] 身后的更大元素
            res[i] = s.isEmpty() ? -1 : s.peek();
            s.push(i);
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(res));
        int[] dd = new int[n];
        Arrays.fill(dd, -1);
        for(int i = n - 3;i >= 0;i--){
            if(res[i] == -1){
                dd[i] = -1;
            }else{
                int end = n - 1;
                int start = res[i] + 1;
                while(start <= end){
                    int mid = start + (end - start) / 2 ;
                    if(nums[mid] > nums[i]){
                        end = mid - 1;
                    }else{
                        start = mid + 1;
                    }
                }
                if(start < nums.length){
                    dd[i] = nums[start];
                }else{
                    dd[i] = -1;
                }
            }
        }
        return dd;
    }

    public static void main(String[] args) {
        SecondGreaterElement secondGreaterElement = new SecondGreaterElement();
        int[] nums = {1,17,18,0,18,10,20,0};
        int[] res = secondGreaterElement.secondGreaterElement(nums);
        System.out.println(Arrays.toString(res));
    }
}
